/*
 * Copyright (C) 2007 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedSet;

import javax.annotation.Nullable;

import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Function;
import com.google.common.base.Joiner;
import com.google.common.base.Joiner.MapJoiner;
import com.google.common.base.Preconditions;
import com.google.common.base.Supplier;

/**
 * Provides static methods acting on or generating a {@code Multimap}.
 * 
 * @author Jared Levy
 * @author Robert Konigsberg
 * @author Mike Bostock
 * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library)
 */
@GwtCompatible
public final class Multimaps {
    private Multimaps() {
    }

    /**
     * Creates a new {@code Multimap} that uses the provided map and factory. It
     * can generate a multimap based on arbitrary {@link Map} and
     * {@link Collection} classes.
     * 
     * <p>
     * The {@code factory}-generated and {@code map} classes determine the
     * multimap iteration order. They also specify the behavior of the
     * {@code equals}, {@code hashCode}, and {@code toString} methods for the
     * multimap and its returned views. However, the multimap's {@code get}
     * method returns instances of a different class than {@code factory.get()}
     * does.
     * 
     * <p>
     * The multimap is serializable if {@code map}, {@code factory}, the
     * collections generated by {@code factory}, and the multimap contents are
     * all serializable.
     * 
     * <p>
     * The multimap is not threadsafe when any concurrent operations update the
     * multimap, even if {@code map} and the instances generated by
     * {@code factory} are. Concurrent read operations will work correctly. To
     * allow concurrent update operations, wrap the multimap with a call to
     * {@link #synchronizedMultimap}.
     * 
     * <p>
     * Call this method only when the simpler methods
     * {@link ArrayListMultimap#create()}, {@link HashMultimap#create()},
     * {@link LinkedHashMultimap#create()}, {@link LinkedListMultimap#create()},
     * {@link TreeMultimap#create()}, and
     * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
     * 
     * <p>
     * Note: the multimap assumes complete ownership over of {@code map} and the
     * collections returned by {@code factory}. Those objects should not be
     * manually updated and they should not use soft, weak, or phantom
     * references.
     * 
     * @param map
     *            place to store the mapping from each key to its corresponding
     *            values
     * @param factory
     *            supplier of new, empty collections that will each hold all
     *            values for a given key
     * @throws IllegalArgumentException
     *             if {@code map} is not empty
     */
    public static <K, V> Multimap<K, V> newMultimap(Map<K, Collection<V>> map,
            final Supplier<? extends Collection<V>> factory) {
        return new CustomMultimap<K, V>(map, factory);
    }

    private static class CustomMultimap<K, V> extends AbstractMultimap<K, V> {
        transient Supplier<? extends Collection<V>> factory;

        CustomMultimap(Map<K, Collection<V>> map,
                Supplier<? extends Collection<V>> factory) {
            super(map);
            this.factory = checkNotNull(factory);
        }

        @Override
        protected Collection<V> createCollection() {
            return factory.get();
        }

        // can't use Serialization writeMultimap and populateMultimap methods
        // since
        // there's no way to generate the empty backing map.

        /** @serialData the factory and the backing map */
        private void writeObject(ObjectOutputStream stream) throws IOException {
            stream.defaultWriteObject();
            stream.writeObject(factory);
            stream.writeObject(backingMap());
        }

        @SuppressWarnings("unchecked")
        // reading data stored by writeObject
        private void readObject(ObjectInputStream stream) throws IOException,
                ClassNotFoundException {
            stream.defaultReadObject();
            factory = (Supplier<? extends Collection<V>>) stream.readObject();
            Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream
                    .readObject();
            setMap(map);
        }

        private static final long serialVersionUID = 0;
    }

    /**
     * Creates a new {@code ListMultimap} that uses the provided map and
     * factory. It can generate a multimap based on arbitrary {@link Map} and
     * {@link List} classes.
     * 
     * <p>
     * The {@code factory}-generated and {@code map} classes determine the
     * multimap iteration order. They also specify the behavior of the
     * {@code equals}, {@code hashCode}, and {@code toString} methods for the
     * multimap and its returned views. The multimap's {@code get},
     * {@code removeAll}, and {@code replaceValues} methods return
     * {@code RandomAccess} lists if the factory does. However, the multimap's
     * {@code get} method returns instances of a different class than does
     * {@code factory.get()}.
     * 
     * <p>
     * The multimap is serializable if {@code map}, {@code factory}, the lists
     * generated by {@code factory}, and the multimap contents are all
     * serializable.
     * 
     * <p>
     * The multimap is not threadsafe when any concurrent operations update the
     * multimap, even if {@code map} and the instances generated by
     * {@code factory} are. Concurrent read operations will work correctly. To
     * allow concurrent update operations, wrap the multimap with a call to
     * {@link #synchronizedListMultimap}.
     * 
     * <p>
     * Call this method only when the simpler methods
     * {@link ArrayListMultimap#create()} and
     * {@link LinkedListMultimap#create()} won't suffice.
     * 
     * <p>
     * Note: the multimap assumes complete ownership over of {@code map} and the
     * lists returned by {@code factory}. Those objects should not be manually
     * updated and they should not use soft, weak, or phantom references.
     * 
     * @param map
     *            place to store the mapping from each key to its corresponding
     *            values
     * @param factory
     *            supplier of new, empty lists that will each hold all values
     *            for a given key
     * @throws IllegalArgumentException
     *             if {@code map} is not empty
     */
    public static <K, V> ListMultimap<K, V> newListMultimap(
            Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) {
        return new CustomListMultimap<K, V>(map, factory);
    }

    private static class CustomListMultimap<K, V> extends
            AbstractListMultimap<K, V> {
        transient Supplier<? extends List<V>> factory;

        CustomListMultimap(Map<K, Collection<V>> map,
                Supplier<? extends List<V>> factory) {
            super(map);
            this.factory = checkNotNull(factory);
        }

        @Override
        protected List<V> createCollection() {
            return factory.get();
        }

        /** @serialData the factory and the backing map */
        private void writeObject(ObjectOutputStream stream) throws IOException {
            stream.defaultWriteObject();
            stream.writeObject(factory);
            stream.writeObject(backingMap());
        }

        @SuppressWarnings("unchecked")
        // reading data stored by writeObject
        private void readObject(ObjectInputStream stream) throws IOException,
                ClassNotFoundException {
            stream.defaultReadObject();
            factory = (Supplier<? extends List<V>>) stream.readObject();
            Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream
                    .readObject();
            setMap(map);
        }

        private static final long serialVersionUID = 0;
    }

    /**
     * Creates a new {@code SetMultimap} that uses the provided map and factory.
     * It can generate a multimap based on arbitrary {@link Map} and {@link Set}
     * classes.
     * 
     * <p>
     * The {@code factory}-generated and {@code map} classes determine the
     * multimap iteration order. They also specify the behavior of the
     * {@code equals}, {@code hashCode}, and {@code toString} methods for the
     * multimap and its returned views. However, the multimap's {@code get}
     * method returns instances of a different class than {@code factory.get()}
     * does.
     * 
     * <p>
     * The multimap is serializable if {@code map}, {@code factory}, the sets
     * generated by {@code factory}, and the multimap contents are all
     * serializable.
     * 
     * <p>
     * The multimap is not threadsafe when any concurrent operations update the
     * multimap, even if {@code map} and the instances generated by
     * {@code factory} are. Concurrent read operations will work correctly. To
     * allow concurrent update operations, wrap the multimap with a call to
     * {@link #synchronizedSetMultimap}.
     * 
     * <p>
     * Call this method only when the simpler methods
     * {@link HashMultimap#create()}, {@link LinkedHashMultimap#create()},
     * {@link TreeMultimap#create()}, and
     * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
     * 
     * <p>
     * Note: the multimap assumes complete ownership over of {@code map} and the
     * sets returned by {@code factory}. Those objects should not be manually
     * updated and they should not use soft, weak, or phantom references.
     * 
     * @param map
     *            place to store the mapping from each key to its corresponding
     *            values
     * @param factory
     *            supplier of new, empty sets that will each hold all values for
     *            a given key
     * @throws IllegalArgumentException
     *             if {@code map} is not empty
     */
    public static <K, V> SetMultimap<K, V> newSetMultimap(
            Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) {
        return new CustomSetMultimap<K, V>(map, factory);
    }

    private static class CustomSetMultimap<K, V> extends
            AbstractSetMultimap<K, V> {
        transient Supplier<? extends Set<V>> factory;

        CustomSetMultimap(Map<K, Collection<V>> map,
                Supplier<? extends Set<V>> factory) {
            super(map);
            this.factory = checkNotNull(factory);
        }

        @Override
        protected Set<V> createCollection() {
            return factory.get();
        }

        /** @serialData the factory and the backing map */
        private void writeObject(ObjectOutputStream stream) throws IOException {
            stream.defaultWriteObject();
            stream.writeObject(factory);
            stream.writeObject(backingMap());
        }

        @SuppressWarnings("unchecked")
        // reading data stored by writeObject
        private void readObject(ObjectInputStream stream) throws IOException,
                ClassNotFoundException {
            stream.defaultReadObject();
            factory = (Supplier<? extends Set<V>>) stream.readObject();
            Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream
                    .readObject();
            setMap(map);
        }

        private static final long serialVersionUID = 0;
    }

    /**
     * Creates a new {@code SortedSetMultimap} that uses the provided map and
     * factory. It can generate a multimap based on arbitrary {@link Map} and
     * {@link SortedSet} classes.
     * 
     * <p>
     * The {@code factory}-generated and {@code map} classes determine the
     * multimap iteration order. They also specify the behavior of the
     * {@code equals}, {@code hashCode}, and {@code toString} methods for the
     * multimap and its returned views. However, the multimap's {@code get}
     * method returns instances of a different class than {@code factory.get()}
     * does.
     * 
     * <p>
     * The multimap is serializable if {@code map}, {@code factory}, the sets
     * generated by {@code factory}, and the multimap contents are all
     * serializable.
     * 
     * <p>
     * The multimap is not threadsafe when any concurrent operations update the
     * multimap, even if {@code map} and the instances generated by
     * {@code factory} are. Concurrent read operations will work correctly. To
     * allow concurrent update operations, wrap the multimap with a call to
     * {@link #synchronizedSortedSetMultimap}.
     * 
     * <p>
     * Call this method only when the simpler methods
     * {@link TreeMultimap#create()} and
     * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
     * 
     * <p>
     * Note: the multimap assumes complete ownership over of {@code map} and the
     * sets returned by {@code factory}. Those objects should not be manually
     * updated and they should not use soft, weak, or phantom references.
     * 
     * @param map
     *            place to store the mapping from each key to its corresponding
     *            values
     * @param factory
     *            supplier of new, empty sorted sets that will each hold all
     *            values for a given key
     * @throws IllegalArgumentException
     *             if {@code map} is not empty
     */
    public static <K, V> SortedSetMultimap<K, V> newSortedSetMultimap(
            Map<K, Collection<V>> map,
            final Supplier<? extends SortedSet<V>> factory) {
        return new CustomSortedSetMultimap<K, V>(map, factory);
    }

    private static class CustomSortedSetMultimap<K, V> extends
            AbstractSortedSetMultimap<K, V> {
        transient Supplier<? extends SortedSet<V>> factory;
        transient Comparator<? super V> valueComparator;

        CustomSortedSetMultimap(Map<K, Collection<V>> map,
                Supplier<? extends SortedSet<V>> factory) {
            super(map);
            this.factory = checkNotNull(factory);
            valueComparator = factory.get().comparator();
        }

        @Override
        protected SortedSet<V> createCollection() {
            return factory.get();
        }

        /* @Override */public Comparator<? super V> valueComparator() {
            return valueComparator;
        }

        /** @serialData the factory and the backing map */
        private void writeObject(ObjectOutputStream stream) throws IOException {
            stream.defaultWriteObject();
            stream.writeObject(factory);
            stream.writeObject(backingMap());
        }

        @SuppressWarnings("unchecked")
        // reading data stored by writeObject
        private void readObject(ObjectInputStream stream) throws IOException,
                ClassNotFoundException {
            stream.defaultReadObject();
            factory = (Supplier<? extends SortedSet<V>>) stream.readObject();
            valueComparator = factory.get().comparator();
            Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream
                    .readObject();
            setMap(map);
        }

        private static final long serialVersionUID = 0;
    }

    /**
     * Copies each key-value mapping in {@code source} into {@code dest}, with
     * its key and value reversed.
     * 
     * @param source
     *            any multimap
     * @param dest
     *            the multimap to copy into; usually empty
     * @return {@code dest}
     */
    public static <K, V, M extends Multimap<K, V>> M invertFrom(
            Multimap<? extends V, ? extends K> source, M dest) {
        for (Map.Entry<? extends V, ? extends K> entry : source.entries()) {
            dest.put(entry.getValue(), entry.getKey());
        }
        return dest;
    }

    /**
     * Returns a synchronized (thread-safe) multimap backed by the specified
     * multimap. In order to guarantee serial access, it is critical that
     * <b>all</b> access to the backing multimap is accomplished through the
     * returned multimap.
     * 
     * <p>
     * It is imperative that the user manually synchronize on the returned
     * multimap when accessing any of its collection views:
     * 
     * <pre>
     * {@code
     * 
     *  Multimap<K, V> m = Multimaps.synchronizedMultimap(
     *      HashMultimap.<K, V>create());
     *  ...
     *  Set<K> s = m.keySet();  // Needn't be in synchronized block
     *  ...
     *  synchronized (m) {  // Synchronizing on m, not s!
     *    Iterator<K> i = s.iterator(); // Must be in synchronized block
     *    while (i.hasNext()) {
     *      foo(i.next());
     *    }
     *  }}
     * </pre>
     * 
     * Failure to follow this advice may result in non-deterministic behavior.
     * 
     * <p>
     * Note that the generated multimap's {@link Multimap#removeAll} and
     * {@link Multimap#replaceValues} methods return collections that aren't
     * synchronized.
     * 
     * <p>
     * The returned multimap will be serializable if the specified multimap is
     * serializable.
     * 
     * @param multimap
     *            the multimap to be wrapped in a synchronized view
     * @return a synchronized view of the specified multimap
     */
    public static <K, V> Multimap<K, V> synchronizedMultimap(
            Multimap<K, V> multimap) {
        return Synchronized.multimap(multimap, null);
    }

    /**
     * Returns an unmodifiable view of the specified multimap. Query operations
     * on the returned multimap "read through" to the specified multimap, and
     * attempts to modify the returned multimap, either directly or through the
     * multimap's views, result in an {@code UnsupportedOperationException}.
     * 
     * <p>
     * Note that the generated multimap's {@link Multimap#removeAll} and
     * {@link Multimap#replaceValues} methods return collections that are
     * modifiable.
     * 
     * <p>
     * The returned multimap will be serializable if the specified multimap is
     * serializable.
     * 
     * @param delegate
     *            the multimap for which an unmodifiable view is to be returned
     * @return an unmodifiable view of the specified multimap
     */
    public static <K, V> Multimap<K, V> unmodifiableMultimap(
            Multimap<K, V> delegate) {
        return new UnmodifiableMultimap<K, V>(delegate);
    }

    private static class UnmodifiableMultimap<K, V> extends
            ForwardingMultimap<K, V> implements Serializable {
        final Multimap<K, V> delegate;
        transient Collection<Entry<K, V>> entries;
        transient Multiset<K> keys;
        transient Set<K> keySet;
        transient Collection<V> values;
        transient Map<K, Collection<V>> map;

        UnmodifiableMultimap(final Multimap<K, V> delegate) {
            this.delegate = delegate;
        }

        @Override
        protected Multimap<K, V> delegate() {
            return delegate;
        }

        @Override
        public void clear() {
            throw new UnsupportedOperationException();
        }

        @Override
        public Map<K, Collection<V>> asMap() {
            Map<K, Collection<V>> result = map;
            if (result == null) {
                final Map<K, Collection<V>> unmodifiableMap = Collections
                        .unmodifiableMap(delegate.asMap());
                map = result = new ForwardingMap<K, Collection<V>>() {
                    @Override
                    protected Map<K, Collection<V>> delegate() {
                        return unmodifiableMap;
                    }

                    Set<Entry<K, Collection<V>>> entrySet;

                    @Override
                    public Set<Map.Entry<K, Collection<V>>> entrySet() {
                        Set<Entry<K, Collection<V>>> result = entrySet;
                        return (result == null) ? entrySet = unmodifiableAsMapEntries(unmodifiableMap
                                .entrySet()) : result;
                    }

                    @Override
                    public Collection<V> get(Object key) {
                        Collection<V> collection = unmodifiableMap.get(key);
                        return (collection == null) ? null
                                : unmodifiableValueCollection(collection);
                    }

                    Collection<Collection<V>> asMapValues;

                    @Override
                    public Collection<Collection<V>> values() {
                        Collection<Collection<V>> result = asMapValues;
                        return (result == null) ? asMapValues = new UnmodifiableAsMapValues<V>(
                                unmodifiableMap.values()) : result;
                    }

                    @Override
                    public boolean containsValue(Object o) {
                        return values().contains(o);
                    }
                };
            }
            return result;
        }

        @Override
        public Collection<Entry<K, V>> entries() {
            Collection<Entry<K, V>> result = entries;
            if (result == null) {
                entries = result = unmodifiableEntries(delegate.entries());
            }
            return result;
        }

        @Override
        public Collection<V> get(K key) {
            return unmodifiableValueCollection(delegate.get(key));
        }

        @Override
        public Multiset<K> keys() {
            Multiset<K> result = keys;
            if (result == null) {
                keys = result = Multisets.unmodifiableMultiset(delegate.keys());
            }
            return result;
        }

        @Override
        public Set<K> keySet() {
            Set<K> result = keySet;
            if (result == null) {
                keySet = result = Collections
                        .unmodifiableSet(delegate.keySet());
            }
            return result;
        }

        @Override
        public boolean put(K key, V value) {
            throw new UnsupportedOperationException();
        }

        @Override
        public boolean putAll(K key, Iterable<? extends V> values) {
            throw new UnsupportedOperationException();
        }

        @Override
        public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
            throw new UnsupportedOperationException();
        }

        @Override
        public boolean remove(Object key, Object value) {
            throw new UnsupportedOperationException();
        }

        @Override
        public Collection<V> removeAll(Object key) {
            throw new UnsupportedOperationException();
        }

        @Override
        public Collection<V> replaceValues(K key, Iterable<? extends V> values) {
            throw new UnsupportedOperationException();
        }

        @Override
        public Collection<V> values() {
            Collection<V> result = values;
            if (result == null) {
                values = result = Collections.unmodifiableCollection(delegate
                        .values());
            }
            return result;
        }

        private static final long serialVersionUID = 0;
    }

    private static class UnmodifiableAsMapValues<V> extends
            ForwardingCollection<Collection<V>> {
        final Collection<Collection<V>> delegate;

        UnmodifiableAsMapValues(Collection<Collection<V>> delegate) {
            this.delegate = Collections.unmodifiableCollection(delegate);
        }

        @Override
        protected Collection<Collection<V>> delegate() {
            return delegate;
        }

        @Override
        public Iterator<Collection<V>> iterator() {
            final Iterator<Collection<V>> iterator = delegate.iterator();
            return new Iterator<Collection<V>>() {
                public boolean hasNext() {
                    return iterator.hasNext();
                }

                public Collection<V> next() {
                    return unmodifiableValueCollection(iterator.next());
                }

                public void remove() {
                    throw new UnsupportedOperationException();
                }
            };
        }

        @Override
        public Object[] toArray() {
            return ObjectArrays.toArrayImpl(this);
        }

        @Override
        public <T> T[] toArray(T[] array) {
            return ObjectArrays.toArrayImpl(this, array);
        }

        @Override
        public boolean contains(Object o) {
            return Iterators.contains(iterator(), o);
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            return Collections2.containsAll(this, c);
        }
    }

    private static class UnmodifiableListMultimap<K, V> extends
            UnmodifiableMultimap<K, V> implements ListMultimap<K, V> {
        UnmodifiableListMultimap(ListMultimap<K, V> delegate) {
            super(delegate);
        }

        @Override
        public ListMultimap<K, V> delegate() {
            return (ListMultimap<K, V>) super.delegate();
        }

        @Override
        public List<V> get(K key) {
            return Collections.unmodifiableList(delegate().get(key));
        }

        @Override
        public List<V> removeAll(Object key) {
            throw new UnsupportedOperationException();
        }

        @Override
        public List<V> replaceValues(K key, Iterable<? extends V> values) {
            throw new UnsupportedOperationException();
        }

        private static final long serialVersionUID = 0;
    }

    private static class UnmodifiableSetMultimap<K, V> extends
            UnmodifiableMultimap<K, V> implements SetMultimap<K, V> {
        UnmodifiableSetMultimap(SetMultimap<K, V> delegate) {
            super(delegate);
        }

        @Override
        public SetMultimap<K, V> delegate() {
            return (SetMultimap<K, V>) super.delegate();
        }

        @Override
        public Set<V> get(K key) {
            /*
             * Note that this doesn't return a SortedSet when delegate is a
             * SortedSetMultiset, unlike (SortedSet<V>) super.get().
             */
            return Collections.unmodifiableSet(delegate().get(key));
        }

        @Override
        public Set<Map.Entry<K, V>> entries() {
            return Maps.unmodifiableEntrySet(delegate().entries());
        }

        @Override
        public Set<V> removeAll(Object key) {
            throw new UnsupportedOperationException();
        }

        @Override
        public Set<V> replaceValues(K key, Iterable<? extends V> values) {
            throw new UnsupportedOperationException();
        }

        private static final long serialVersionUID = 0;
    }

    private static class UnmodifiableSortedSetMultimap<K, V> extends
            UnmodifiableSetMultimap<K, V> implements SortedSetMultimap<K, V> {
        UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) {
            super(delegate);
        }

        @Override
        public SortedSetMultimap<K, V> delegate() {
            return (SortedSetMultimap<K, V>) super.delegate();
        }

        @Override
        public SortedSet<V> get(K key) {
            return Collections.unmodifiableSortedSet(delegate().get(key));
        }

        @Override
        public SortedSet<V> removeAll(Object key) {
            throw new UnsupportedOperationException();
        }

        @Override
        public SortedSet<V> replaceValues(K key, Iterable<? extends V> values) {
            throw new UnsupportedOperationException();
        }

        public Comparator<? super V> valueComparator() {
            return delegate().valueComparator();
        }

        private static final long serialVersionUID = 0;
    }

    /**
     * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the
     * specified multimap.
     * 
     * <p>
     * You must follow the warnings described in {@link #synchronizedMultimap}.
     * 
     * <p>
     * The returned multimap will be serializable if the specified multimap is
     * serializable.
     * 
     * @param multimap
     *            the multimap to be wrapped
     * @return a synchronized view of the specified multimap
     */
    public static <K, V> SetMultimap<K, V> synchronizedSetMultimap(
            SetMultimap<K, V> multimap) {
        return Synchronized.setMultimap(multimap, null);
    }

    /**
     * Returns an unmodifiable view of the specified {@code SetMultimap}. Query
     * operations on the returned multimap "read through" to the specified
     * multimap, and attempts to modify the returned multimap, either directly
     * or through the multimap's views, result in an
     * {@code UnsupportedOperationException}.
     * 
     * <p>
     * Note that the generated multimap's {@link Multimap#removeAll} and
     * {@link Multimap#replaceValues} methods return collections that are
     * modifiable.
     * 
     * <p>
     * The returned multimap will be serializable if the specified multimap is
     * serializable.
     * 
     * @param delegate
     *            the multimap for which an unmodifiable view is to be returned
     * @return an unmodifiable view of the specified multimap
     */
    public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
            SetMultimap<K, V> delegate) {
        return new UnmodifiableSetMultimap<K, V>(delegate);
    }

    /**
     * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by
     * the specified multimap.
     * 
     * <p>
     * You must follow the warnings described in {@link #synchronizedMultimap}.
     * 
     * <p>
     * The returned multimap will be serializable if the specified multimap is
     * serializable.
     * 
     * @param multimap
     *            the multimap to be wrapped
     * @return a synchronized view of the specified multimap
     */
    public static <K, V> SortedSetMultimap<K, V> synchronizedSortedSetMultimap(
            SortedSetMultimap<K, V> multimap) {
        return Synchronized.sortedSetMultimap(multimap, null);
    }

    /**
     * Returns an unmodifiable view of the specified {@code SortedSetMultimap}.
     * Query operations on the returned multimap "read through" to the specified
     * multimap, and attempts to modify the returned multimap, either directly
     * or through the multimap's views, result in an
     * {@code UnsupportedOperationException}.
     * 
     * <p>
     * Note that the generated multimap's {@link Multimap#removeAll} and
     * {@link Multimap#replaceValues} methods return collections that are
     * modifiable.
     * 
     * <p>
     * The returned multimap will be serializable if the specified multimap is
     * serializable.
     * 
     * @param delegate
     *            the multimap for which an unmodifiable view is to be returned
     * @return an unmodifiable view of the specified multimap
     */
    public static <K, V> SortedSetMultimap<K, V> unmodifiableSortedSetMultimap(
            SortedSetMultimap<K, V> delegate) {
        return new UnmodifiableSortedSetMultimap<K, V>(delegate);
    }

    /**
     * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the
     * specified multimap.
     * 
     * <p>
     * You must follow the warnings described in {@link #synchronizedMultimap}.
     * 
     * @param multimap
     *            the multimap to be wrapped
     * @return a synchronized view of the specified multimap
     */
    public static <K, V> ListMultimap<K, V> synchronizedListMultimap(
            ListMultimap<K, V> multimap) {
        return Synchronized.listMultimap(multimap, null);
    }

    /**
     * Returns an unmodifiable view of the specified {@code ListMultimap}. Query
     * operations on the returned multimap "read through" to the specified
     * multimap, and attempts to modify the returned multimap, either directly
     * or through the multimap's views, result in an
     * {@code UnsupportedOperationException}.
     * 
     * <p>
     * Note that the generated multimap's {@link Multimap#removeAll} and
     * {@link Multimap#replaceValues} methods return collections that are
     * modifiable.
     * 
     * <p>
     * The returned multimap will be serializable if the specified multimap is
     * serializable.
     * 
     * @param delegate
     *            the multimap for which an unmodifiable view is to be returned
     * @return an unmodifiable view of the specified multimap
     */
    public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
            ListMultimap<K, V> delegate) {
        return new UnmodifiableListMultimap<K, V>(delegate);
    }

    /**
     * Returns an unmodifiable view of the specified collection, preserving the
     * interface for instances of {@code SortedSet}, {@code Set}, {@code List}
     * and {@code Collection}, in that order of preference.
     * 
     * @param collection
     *            the collection for which to return an unmodifiable view
     * @return an unmodifiable view of the collection
     */
    private static <V> Collection<V> unmodifiableValueCollection(
            Collection<V> collection) {
        if (collection instanceof SortedSet) {
            return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
        } else if (collection instanceof Set) {
            return Collections.unmodifiableSet((Set<V>) collection);
        } else if (collection instanceof List) {
            return Collections.unmodifiableList((List<V>) collection);
        }
        return Collections.unmodifiableCollection(collection);
    }

    /**
     * Returns an unmodifiable view of the specified multimap {@code asMap}
     * entry. The {@link Entry#setValue} operation throws an
     * {@link UnsupportedOperationException}, and the collection returned by
     * {@code getValue} is also an unmodifiable (type-preserving) view. This
     * also has the side-effect of redefining equals to comply with the
     * Map.Entry contract, and to avoid a possible nefarious implementation of
     * equals.
     * 
     * @param entry
     *            the entry for which to return an unmodifiable view
     * @return an unmodifiable view of the entry
     */
    private static <K, V> Map.Entry<K, Collection<V>> unmodifiableAsMapEntry(
            final Map.Entry<K, Collection<V>> entry) {
        checkNotNull(entry);
        return new AbstractMapEntry<K, Collection<V>>() {
            @Override
            public K getKey() {
                return entry.getKey();
            }

            @Override
            public Collection<V> getValue() {
                return unmodifiableValueCollection(entry.getValue());
            }
        };
    }

    /**
     * Returns an unmodifiable view of the specified collection of entries. The
     * {@link Entry#setValue} operation throws an
     * {@link UnsupportedOperationException}. If the specified collection is a
     * {@code Set}, the returned collection is also a {@code Set}.
     * 
     * @param entries
     *            the entries for which to return an unmodifiable view
     * @return an unmodifiable view of the entries
     */
    private static <K, V> Collection<Entry<K, V>> unmodifiableEntries(
            Collection<Entry<K, V>> entries) {
        if (entries instanceof Set) {
            return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries);
        }
        return new Maps.UnmodifiableEntries<K, V>(
                Collections.unmodifiableCollection(entries));
    }

    /**
     * Returns an unmodifiable view of the specified set of {@code asMap}
     * entries. The {@link Entry#setValue} operation throws an
     * {@link UnsupportedOperationException}, as do any operations that attempt
     * to modify the returned collection.
     * 
     * @param asMapEntries
     *            the {@code asMap} entries for which to return an unmodifiable
     *            view
     * @return an unmodifiable view of the collection entries
     */
    private static <K, V> Set<Entry<K, Collection<V>>> unmodifiableAsMapEntries(
            Set<Entry<K, Collection<V>>> asMapEntries) {
        return new UnmodifiableAsMapEntries<K, V>(
                Collections.unmodifiableSet(asMapEntries));
    }

    /** @see Multimaps#unmodifiableAsMapEntries */
    static class UnmodifiableAsMapEntries<K, V> extends
            ForwardingSet<Entry<K, Collection<V>>> {
        private final Set<Entry<K, Collection<V>>> delegate;

        UnmodifiableAsMapEntries(Set<Entry<K, Collection<V>>> delegate) {
            this.delegate = delegate;
        }

        @Override
        protected Set<Entry<K, Collection<V>>> delegate() {
            return delegate;
        }

        @Override
        public Iterator<Entry<K, Collection<V>>> iterator() {
            final Iterator<Entry<K, Collection<V>>> iterator = delegate
                    .iterator();
            return new ForwardingIterator<Entry<K, Collection<V>>>() {
                @Override
                protected Iterator<Entry<K, Collection<V>>> delegate() {
                    return iterator;
                }

                @Override
                public Entry<K, Collection<V>> next() {
                    return unmodifiableAsMapEntry(iterator.next());
                }
            };
        }

        @Override
        public Object[] toArray() {
            return ObjectArrays.toArrayImpl(this);
        }

        @Override
        public <T> T[] toArray(T[] array) {
            return ObjectArrays.toArrayImpl(this, array);
        }

        @Override
        public boolean contains(Object o) {
            return Maps.containsEntryImpl(delegate(), o);
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            return Collections2.containsAll(this, c);
        }

        @Override
        public boolean equals(@Nullable Object object) {
            return Collections2.setEquals(this, object);
        }
    }

    /**
     * Returns a multimap view of the specified map. The multimap is backed by
     * the map, so changes to the map are reflected in the multimap, and vice
     * versa. If the map is modified while an iteration over one of the
     * multimap's collection views is in progress (except through the iterator's
     * own {@code remove} operation, or through the {@code setValue} operation
     * on a map entry returned by the iterator), the results of the iteration
     * are undefined.
     * 
     * <p>
     * The multimap supports mapping removal, which removes the corresponding
     * mapping from the map. It does not support any operations which might add
     * mappings, such as {@code put}, {@code putAll} or {@code replaceValues}.
     * 
     * <p>
     * The returned multimap will be serializable if the specified map is
     * serializable.
     * 
     * @param map
     *            the backing map for the returned multimap view
     */
    public static <K, V> SetMultimap<K, V> forMap(Map<K, V> map) {
        return new MapMultimap<K, V>(map);
    }

    /** @see Multimaps#forMap */
    private static class MapMultimap<K, V> implements SetMultimap<K, V>,
            Serializable {
        final Map<K, V> map;
        transient Map<K, Collection<V>> asMap;

        MapMultimap(Map<K, V> map) {
            this.map = checkNotNull(map);
        }

        public int size() {
            return map.size();
        }

        public boolean isEmpty() {
            return map.isEmpty();
        }

        public boolean containsKey(Object key) {
            return map.containsKey(key);
        }

        public boolean containsValue(Object value) {
            return map.containsValue(value);
        }

        public boolean containsEntry(Object key, Object value) {
            return map.entrySet().contains(Maps.immutableEntry(key, value));
        }

        public Set<V> get(final K key) {
            return new AbstractSet<V>() {
                @Override
                public Iterator<V> iterator() {
                    return new Iterator<V>() {
                        int i;

                        public boolean hasNext() {
                            return (i == 0) && map.containsKey(key);
                        }

                        public V next() {
                            if (!hasNext()) {
                                throw new NoSuchElementException();
                            }
                            i++;
                            return map.get(key);
                        }

                        public void remove() {
                            checkState(i == 1);
                            i = -1;
                            map.remove(key);
                        }
                    };
                }

                @Override
                public int size() {
                    return map.containsKey(key) ? 1 : 0;
                }
            };
        }

        public boolean put(K key, V value) {
            throw new UnsupportedOperationException();
        }

        public boolean putAll(K key, Iterable<? extends V> values) {
            throw new UnsupportedOperationException();
        }

        public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
            throw new UnsupportedOperationException();
        }

        public Set<V> replaceValues(K key, Iterable<? extends V> values) {
            throw new UnsupportedOperationException();
        }

        public boolean remove(Object key, Object value) {
            return map.entrySet().remove(Maps.immutableEntry(key, value));
        }

        public Set<V> removeAll(Object key) {
            Set<V> values = new HashSet<V>(2);
            if (!map.containsKey(key)) {
                return values;
            }
            values.add(map.remove(key));
            return values;
        }

        public void clear() {
            map.clear();
        }

        public Set<K> keySet() {
            return map.keySet();
        }

        public Multiset<K> keys() {
            return Multisets.forSet(map.keySet());
        }

        public Collection<V> values() {
            return map.values();
        }

        public Set<Entry<K, V>> entries() {
            return map.entrySet();
        }

        public Map<K, Collection<V>> asMap() {
            Map<K, Collection<V>> result = asMap;
            if (result == null) {
                asMap = result = new AsMap();
            }
            return result;
        }

        @Override
        public boolean equals(@Nullable Object object) {
            if (object == this) {
                return true;
            }
            if (object instanceof Multimap) {
                Multimap<?, ?> that = (Multimap<?, ?>) object;
                return this.size() == that.size()
                        && asMap().equals(that.asMap());
            }
            return false;
        }

        @Override
        public int hashCode() {
            return map.hashCode();
        }

        private static final MapJoiner joiner = Joiner.on("], ")
                .withKeyValueSeparator("=[").useForNull("null");

        @Override
        public String toString() {
            if (map.isEmpty()) {
                return "{}";
            }
            StringBuilder builder = new StringBuilder(map.size() * 16)
                    .append('{');
            joiner.appendTo(builder, map);
            return builder.append("]}").toString();
        }

        /** @see MapMultimap#asMap */
        class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> {
            @Override
            public int size() {
                return map.size();
            }

            @Override
            public Iterator<Entry<K, Collection<V>>> iterator() {
                return new Iterator<Entry<K, Collection<V>>>() {
                    final Iterator<K> keys = map.keySet().iterator();

                    public boolean hasNext() {
                        return keys.hasNext();
                    }

                    public Entry<K, Collection<V>> next() {
                        final K key = keys.next();
                        return new AbstractMapEntry<K, Collection<V>>() {
                            @Override
                            public K getKey() {
                                return key;
                            }

                            @Override
                            public Collection<V> getValue() {
                                return get(key);
                            }
                        };
                    }

                    public void remove() {
                        keys.remove();
                    }
                };
            }

            @Override
            public boolean contains(Object o) {
                if (!(o instanceof Entry)) {
                    return false;
                }
                Entry<?, ?> entry = (Entry<?, ?>) o;
                if (!(entry.getValue() instanceof Set)) {
                    return false;
                }
                Set<?> set = (Set<?>) entry.getValue();
                return (set.size() == 1)
                        && containsEntry(entry.getKey(), set.iterator().next());
            }

            @Override
            public boolean remove(Object o) {
                if (!(o instanceof Entry)) {
                    return false;
                }
                Entry<?, ?> entry = (Entry<?, ?>) o;
                if (!(entry.getValue() instanceof Set)) {
                    return false;
                }
                Set<?> set = (Set<?>) entry.getValue();
                return (set.size() == 1)
                        && map.entrySet().remove(
                                Maps.immutableEntry(entry.getKey(), set
                                        .iterator().next()));
            }
        }

        /** @see MapMultimap#asMap */
        class AsMap extends Maps.ImprovedAbstractMap<K, Collection<V>> {
            @Override
            protected Set<Entry<K, Collection<V>>> createEntrySet() {
                return new AsMapEntries();
            }

            // The following methods are included for performance.

            @Override
            public boolean containsKey(Object key) {
                return map.containsKey(key);
            }

            @SuppressWarnings("unchecked")
            @Override
            public Collection<V> get(Object key) {
                Collection<V> collection = MapMultimap.this.get((K) key);
                return collection.isEmpty() ? null : collection;
            }

            @Override
            public Collection<V> remove(Object key) {
                Collection<V> collection = removeAll(key);
                return collection.isEmpty() ? null : collection;
            }
        }

        private static final long serialVersionUID = 7845222491160860175L;
    }

    /**
     * Creates an index {@code ImmutableMultimap} that contains the results of
     * applying a specified function to each item in an {@code Iterable} of
     * values. Each value will be stored as a value in the resulting multimap,
     * yielding a multimap with the same size as the input iterable. The key
     * used to store that value in the multimap will be the result of calling
     * the function on that value. The resulting multimap is created as an
     * immutable snapshot, it does <em>not</em> reflect subsequent changes on
     * the input iterable.
     * 
     * <p>
     * For example,
     * 
     * <pre class="code">
     * {@code
     * 
     *  List<String> badGuys
     *      = Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
     *  Function<String, Integer> stringLengthFunction = ...;
     *  Multimap<Integer, String> index
     *      = Multimaps.index(badGuys, stringLengthFunction);
     *  System.out.println(index);}
     * </pre>
     * 
     * prints
     * 
     * <pre class="code">
     * {@code
     * 
     *  {4=[Inky], 5=[Pinky, Pinky, Clyde], 6=[Blinky]}}
     * </pre>
     * 
     * <p>
     * The returned multimap is serializable if its keys and values are all
     * serializable.
     * 
     * @param values
     *            the values to use when constructing the
     *            {@code ImmutableMultimap}
     * @param keyFunction
     *            the function used to produce the key for each value
     * @return {@code ImmutableMultimap} mapping the result of evaluating the
     *         function {@code keyFunction} on each value in the input
     *         collection to that value
     * @throws NullPointerException
     *             if any of the following cases is true:
     *             <ul>
     *             <li> {@code values} is null <li> {@code keyFunction} is null
     *             <li> An element in {@code values} is null <li>
     *             {@code keyFunction} returns null for any element of
     *             {@code values}
     *             </ul>
     */
    public static <K, V> ImmutableListMultimap<K, V> index(Iterable<V> values,
            Function<? super V, K> keyFunction) {
        checkNotNull(keyFunction);
        ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap
                .builder();
        for (V value : values) {
            Preconditions.checkNotNull(value, values);
            builder.put(keyFunction.apply(value), value);
        }
        return builder.build();
    }
}
